Let q=pr be a prime power and Fq be the finite field with q elements. We study the multiplication of two polynomials in Fq [X], with degree ≤ n-1, modulo an irreducible polynomial of degree n, namely the multiplication in the finite field Fqn.
We want to find a multiplication algorithm involving two variables in Fqn minimizing the number of bilinear multiplications (i.e. involving two variables) in Fq. We don't take in account multiplications of a variable in Fq by a constant in Fq (However these linear operations have a cost).
It turns out that the number of bilinear operations is related to a tensor expression of the multiplication and that the problem is to find the rank of this tensor.
We will give, using interpolation on algebraic curves over the finite field Fq, a sharp estimate for this bilinear complexity.